Ricerca e ordinamento: la base per grandi quantità di dati

Ricerca e ordinamento non sono solo l'introduzione ai corsi di algoritmi, ma rappresentano anche la logica fondamentale con cui la scienza informatica gestisce i dati. Il valore dei dati dipende dall'efficienza con cui vengono recuperati e organizzati. In questo capitolo viene illustrato il concetto più basilare diricerca lineareil nucleo della valutazione degli algoritmi — ovvero come, in diversi tipi di dati, utilizzare confronti lineari per localizzare un obiettivo.

1. Logica e costo

Ricerca lineare:Si inizia dal primo elemento della lista e si procede sequenzialmente fino a trovare l'elemento cercato o fino alla fine della lista. La complessità temporale è $O(n)$.

2. Confronto delle prestazioni: disordinato vs ordinato

Nelelenco disordinato中（见下表），无论成功与否，平均比对次数通常与 $n$ 成正比。而在elenco ordinatosi può ottenere una "uscita anticipata" sfruttando le regole di ordinamento: quando si incontra un elemento maggiore del valore cercato, si può concludere che l'obiettivo non esiste. Anche se ciò non cambia la complessità fondamentale $O(n)$, migliora l'efficienza media della ricerca fallita.